namespace hjc {
	export class AStarSearcher {

		private $map: AStarMap;
		private $start: AStarNode;		//当前起点
		private $goal: AStarNode;		//当前终点
		private $closed: AStarNode[];	//关闭节点
		private $open: AStarNode[];		//开启节点
		private $avgCost: number;		//平局花费
		private $nodes: Map<string, AStarNode>;//地图节点	
		constructor(map: AStarMap) {
			this.$map = map;
			this.$nodes = new Map();
			this.$avgCost = AStarNode.DFT_NODE_COST;
		}
		public get start(): AStarNode { return this.$start; }
		public get goal(): AStarNode { return this.$goal; }
		public get avgCost(): number { return this.$avgCost; }
		public getNode(col: number, row: number): AStarNode { return this.$nodes.get(`${col}_${row}`); }
		public clear(): void {
			this.$nodes.forEach(node => game.free(node));
			this.$nodes.clear();
		}
		public ucNode(col: number, row: number, x: number, y: number, data?: number): void {
			if (this.getNode(col, row)) this.getNode(col, row).init(col, row, x, y, data);
			else this.$nodes.set(`${col}_${row}`, game.claim(AStarNode, col, row, x, y, data));
		}
		public search(start: AStarNode, goal: AStarNode): AStarPath | null {
			if (!start || !goal) return null;
			if (!start.walkable) return null;
			this.$goal = goal; this.$goal.former = null;
			this.$start = start; this.$start.G = 0; this.$start.former = null;
			this.$start.F = this.$map.strategy.calc(start, goal);
			this.$open = [this.$start]; this.$closed = [];	//构造开启和关闭节点数组
			this._calcAvgCost();
			//开始遍历开启节点组
			while (notEmptyArr(this.$open)) {
				//寻找最小总代价节点
				let current = this._findMinF();
				this.$open.remove(current); this.$closed.push(current);
				if (current === goal) break;
				else this._getNeighbors(current).forEach((neighbor: AStarNode) => {
					if (neighbor.walkable && this.$closed.excludes(neighbor)) {
						let h = this.$map.strategy.calc(neighbor, this.$goal);
						if (this.$open.excludes(neighbor)) this.$open.push(neighbor.update(current, h));
						else if (neighbor.G > current.G + h) neighbor.update(current, h);
					}
				});
			}
			if (this.$goal.former) return new AStarPath(this.$goal, this.$map);
			else return null;
		}

		private _findMinF(): AStarNode {
			let min = this.$open.head();
			let f = min.F;
			this.$open.forEach((node: AStarNode) => {
				if (node.F < f) { min = node; f = min.F; }
			});
			return min;
		}

		private _getNeighbors(node: AStarNode): AStarNode[] {
			let pairs: number[][] = [[node.col, node.row - 1], [node.col, node.row + 1], [node.col - 1, node.row], [node.col + 1, node.row]];
			if (this.$map.allow8) pairs.push([node.col - 1, node.row - 1], [node.col + 1, node.row - 1], [node.col + 1, node.row + 1], [node.col - 1, node.row + 1]);
			let neighbors: AStarNode[] = [];
			pairs.forEach(([col, row]) => this.$map.getNode(col, row) ? neighbors.push(this.$map.getNode(col, row)) : null);
			return neighbors;
		}

		private _calcAvgCost(): void {
			let sum = 0;
			this.$nodes.forEach((node) => sum += node.cost);
			this.$avgCost = sum / this.$map.size;
		}

	}
}